package leecode

import "container/list"

type Node116 struct {
	Val   int
	Left  *Node116
	Right *Node116
	Next  *Node116
}

func connect(root *Node116) (result *Node116) {
	if root == nil {
		return
	}
	result = root
	queue := list.New()
	queue.PushBack(root)
	for queue.Len() != 0 {
		size := queue.Len()
		temp := make([]*Node116, 0)
		for i := 0; i < size; i++ {
			node := queue.Remove(queue.Front()).(*Node116)
			if node.Left != nil {
				queue.PushBack(node.Left)
			}
			if node.Right != nil {
				queue.PushBack(node.Right)
			}
			temp = append(temp, node)
		}
		if len(temp) > 1 {
			//遍历每一层元素
			for i := 0; i < len(temp)-1; i++ {
				temp[i].Next = temp[i+1]
			}
		}
	}
	return
}
